package com.example.leetcode.子串;

import java.util.HashMap;
import java.util.Map;

/**
 * 和为 K 的子数组
 * 给你一个整数数组 nums 和一个整数 k ，请你统计并返回 该数组中和为 k 的子数组的个数 。
 * 子数组是数组中元素的连续非空序列。
 * 示例 1：
 * 输入：nums = [1,1,1], k = 2
 * 输出：2
 * <p>
 * 示例 2：
 * 输入：nums = [1,2,3], k = 3
 * 输出：2
 * <p>
 * 思路：
 * 假设数组的前缀和数组为prefixSum，其中prefixSum[i]表示从数组起始位置到第i个位置的元素之和。
 * 那么对于任意的两个下标i和j（i < j），如果prefixSum[j] - prefixSum[i] = k，即从第i个位置到第j个位置的元素之和等于k，
 * 那么说明从第i+1个位置到第j个位置的连续子数组的和为k。
 * <p>
 * 通过遍历数组，计算每个位置的前缀和，并使用一个哈希表来存储每个前缀和出现的次数。在遍历的过程中，我们检查是否存在prefixSum[j] - k的前缀和，
 * 如果存在，说明从某个位置到当前位置的连续子数组的和为k，我们将对应的次数累加到结果中。
 * <p>
 * 这样，通过遍历一次数组，我们可以统计出和为k的连续子数组的个数，并且时间复杂度为O(n)，其中n为数组的长度。
 */
public class SubarraySum {

    public static void main(String[] args) {
        int[] nums = new int[]{1, 1, 1};
        int i = subarraySum(nums, 2);
    }


    public static int subarraySum2(int[] nums, int k) {
        int result = 0;
        int pre = 0;
        Map<Integer, Integer> map = new HashMap<>();
        map.put(0, 1);

        for (int num : nums) {
            // 前缀和
            pre += num;
            // 当前前缀和 - 之前的前缀和 =k
            if (map.containsKey(pre - k)) {
                result += map.get(pre - k);
            }

            // key前缀和，value是出现次数
            map.put(pre, map.getOrDefault(pre, 0) + 1);
        }

        return result;
    }


    public static int subarraySum(int[] nums, int k) {
        int count = 0, pre = 0;
        HashMap<Integer, Integer> mp = new HashMap<>();
        mp.put(0, 1);
        for (int i = 0; i < nums.length; i++) {
            // 计算前缀和
            pre += nums[i];
            // 当前前缀和 - 之前的前缀和 = k
            if (mp.containsKey(pre - k)) {
                count += mp.get(pre - k);
            }
            // 前缀和作为key, value是前缀和出现的次数
            mp.put(pre, mp.getOrDefault(pre, 0) + 1);
        }
        return count;
    }

}
